package com.cdream.basic.algorithm.leetcode.slideWindow;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cdream
 * @date 5/20/21
 */
public class Question76 {
    Map<Character, Integer> window = new HashMap<Character, Integer>();
    Map<Character, Integer> tMap = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        String res = "";
        // 把被包含的串初始化到Map中
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        int l = 0;
        int r = -1;

        int len = Integer.MAX_VALUE, resL = -1, resR = -1;


        while (r < s.length()) {
            ++r;

            if (r < s.length() && tMap.containsKey(s.charAt(r))) {
                window.put(s.charAt(r), window.getOrDefault(s.charAt(r), 0) + 1);
            }

            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    resL = l;
                    resR = l + len;
                }
                if (tMap.containsKey(s.charAt(l))) {
                    window.put(s.charAt(l), window.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return resL == -1 ? "" : s.substring(resL, resR);

    }

    private boolean check() {
        for (Map.Entry<Character, Integer> characterIntegerEntry : tMap.entrySet()) {
            Character key = (Character) ((Map.Entry) characterIntegerEntry).getKey();
            Integer val = (Integer) ((Map.Entry) characterIntegerEntry).getValue();
            if (window.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}
